package Classic150;

public class 建立四叉树 {

    /*
        递归构造
     */
    int[][] grid;

    public Node construct(int[][] grid) {
        this.grid = grid;
        return dfs(0, grid.length, 0, grid.length);
    }

    public Node dfs(int up, int down, int left, int right) {
        boolean isSame = true;
        int num = grid[up][left];
        for (int i = up; i < down; i++) {
            for (int j = left; j < right; j++) {
                if (grid[i][j] != num) {
                    isSame = false;
                    break;
                }
            }
            if (!isSame) break;
        }
        if (isSame) return new Node(num == 1, true);
        return new Node (
                true,
                false,
                dfs(left, (left + right) / 2, up, (up + down) / 2),
                dfs((left + right) / 2, right, up, (up + down) / 2),
                dfs(left, (left + right) / 2, (up + down) / 2, down),
                dfs((left + right) / 2, right, (up + down) / 2, down)
        );
    }
}

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;


    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}
